#include <vector>
#include <queue>
#include <unordered_set>
#include <string>
#include <sstream>
#include <algorithm>
#include <unordered_set>
using namespace std;

struct ComparePath {
    bool operator()(const pair<int, vector<int>>& a, const pair<int, vector<int>>& b) {
        return a.first > b.first;
    }
};

int pathLength(const vector<int>& path, int** roadlength) {
    int length = 0;
    for (size_t i = 0; i < path.size() - 1; ++i) {
        length += roadlength[path[i]][path[i+1]];
    }
    return length;
}

string pathToString(const vector<int>& path) {
    stringstream ss;
    for (int node : path) {
        ss << node << ",";
    }
    return ss.str();
}

vector<int> dijkstra(int N, int start, int end, int** roadlength, unordered_set<pair<int, int>> forbiddenEdges) {
    int *distance = new int[N];
    int *previous = new int[N];
    bool *visited = new bool[N];

    for (int i = 0; i < N; i++) {
        distance[i] = roadlength[start][i];
        visited[i] = false;
        if (i != start && distance[i] < INT_MAX) {
            previous[i] = start;
        } else {
            previous[i] = -1;
        }
    }
    distance[start] = 0;
    visited[start] = true;

    for (int i = 0; i < N - 1; i++) {
        int min_distance = INT_MAX;
        int stop = start;
        for (int j = 0; j < N; j++) {
            if (!visited[j] && distance[j] < min_distance) {
                min_distance = distance[j];
                stop = j;
            }
        }
        visited[stop] = true;
        for (int k = 0; k < N; k++) {
            if (!visited[k] && roadlength[stop][k] < INT_MAX) {
                pair<int, int> edge = make_pair(stop, k);
                if (forbiddenEdges.find(edge) == forbiddenEdges.end()) {
                    if (distance[stop] + roadlength[stop][k] < distance[k]) {
                        distance[k] = distance[stop] + roadlength[stop][k];
                        previous[k] = stop;
                    }
                }
            }
        }
    }

    vector<int> path;
    int node = end;
    while (node != -1) {
        path.push_back(node);
        node = previous[node];
    }
    reverse(path.begin(), path.end());
    delete[] distance;
    delete[] previous;
    delete[] visited;
    return path;
}

vector<vector<int>> YenKSP(int N, int start, int end, int** roadlength, int K) {
    vector<vector<int>> P;
    vector<int> P1 = dijkstra(N, start, end, roadlength, unordered_set<pair<int, int>>());
    P.push_back(P1);
    if (K == 1) {
        return P;
    }

    unordered_set<string> existingPaths;
    existingPaths.insert(pathToString(P1));

    for (int i = 1; i < K; ++i) {
        priority_queue<pair<int, vector<int>>, vector<pair<int, vector<int>>>, ComparePath> B;

        for (const auto& p : P) {
            for (size_t j = 0; j < p.size() - 1; ++j) {
                int u = p[j];
                int v = p[j+1];
                vector<int> rootPath(p.begin(), p.begin() + j + 1);
                unordered_set<pair<int, int>> forbiddenEdges;
                forbiddenEdges.insert(make_pair(u, v));
                for (const auto& q : P) {
                    if (q.size() > j && equal(q.begin(), q.begin() + j + 1, p.begin())) {
                        if (q.size() > j + 1) {
                            forbiddenEdges.insert(make_pair(q[j], q[j+1]));
                        }
                    }
                }
                vector<int> spurPath = dijkstra(N, u, end, roadlength, forbiddenEdges);
                if (!spurPath.empty()) {
                    vector<int> totalPath;
                    totalPath.insert(totalPath.end(), rootPath.begin(), rootPath.end());
                    if (!spurPath.empty()) {
                        totalPath.insert(totalPath.end(), spurPath.begin() + 1, spurPath.end());
                    }
                    string pathStr = pathToString(totalPath);
                    if (existingPaths.find(pathStr) == existingPaths.end()) {
                        int pathLen = pathLength(totalPath, roadlength);
                        B.push(make_pair(pathLen, totalPath));
                        existingPaths.insert(pathStr);
                    }
                }
            }
        }

        if (B.empty()) {
            break;
        }

        pair<int, vector<int>> nextPath = B.top();
        B.pop();
        P.push_back(nextPath.second);
        existingPaths.insert(pathToString(nextPath.second));
    }

    return P;
}